﻿#region File Header
/***********************************************************************
 * Copyright © 2012 Beals Software
 * All Rights Reserved
************************************************************************
Author: Donald Beals
Date: Month Day, Year
Description: TODO: Write a description of this file here.
****************************** Change Log ******************************
MM.DD.YY - Created initial file. (dbeals)
***********************************************************************/
#endregion

#region Using Statements
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
#endregion

namespace PolygonBasedPathfinding
{
	/// <summary>
	/// 
	/// </summary>
	public sealed class Pathfinder
	{
		#region Variables
		#endregion

		#region Properties
		public bool TrimPaths
		{
			get;
			set;
		}

		public Func<int, int, bool> CheckNode
		{
			get;
			set;
		}
		#endregion

		#region Constructors
		public Pathfinder()
		{
		}
		#endregion

		#region Methods
		private Point[] CreatePath(PathTreeNode node, out int depth)
		{
			var output = new List<Point>();
			var parent = node;
			while(parent != null)
			{
				output.Insert(0, parent.Position);
				parent = parent.Parent;
			}
			depth = output.Count;

			if(TrimPaths)
			{
				var indicesToRemove = new List<int>();
				for(var index = 1; index < output.Count - 1; ++index)
				{
					var previousPoint = output[index - 1];
					var currentPoint = output[index];
					var nextPoint = output[index + 1];

					if(
						(currentPoint.X == nextPoint.X && currentPoint.Y != nextPoint.Y && nextPoint.X == previousPoint.X) ||
						(currentPoint.Y == nextPoint.Y && currentPoint.X != nextPoint.X && nextPoint.Y == previousPoint.Y))
						indicesToRemove.Add(index);
				}

				for(var index = indicesToRemove.Count - 1; index >= 0; --index)
					output.RemoveAt(indicesToRemove[index]);
			}
			return output.ToArray();
		}

		private bool CheckNodeList(IEnumerable<PathTreeNode> nodes, Point point)
		{
			return CheckNodeList(nodes, point.X, point.Y);
		}

		private bool CheckNodeList(IEnumerable<PathTreeNode> nodes, int column, int row)
		{
			foreach(var node in nodes)
			{
				if(node.Position.X == column && node.Position.Y == row)
					return true;
			}
			return false;
		}

		private PathTreeNode ProcessNode(PathTreeNode currentNode, int columnOffset, int rowOffset, List<PathTreeNode> openNodes, List<PathTreeNode> closedNodes)
		{
			var newNode = new PathTreeNode(currentNode.Position.X + columnOffset, currentNode.Position.Y + rowOffset, currentNode, 0);
			if((CheckNode == null || CheckNode(newNode.Position.X, newNode.Position.Y)) &&
				!CheckNodeList(closedNodes, newNode.Position) &&
				!CheckNodeList(openNodes, newNode.Position))
			{
				openNodes.Add(newNode);
				return newNode;
			}
			return null;
		}

		public Point[] FindPath(int startColumn, int startRow, int endColumn, int endRow, out int depth)
		{
			return FindPath(new Point(startColumn, startRow), new Point(endColumn, endRow), out depth);
		}

		public Point[] FindPath(Point startPosition, Point endPosition, out int depth)
		{
			var closedNodes = new List<PathTreeNode>();
			var openNodes = new List<PathTreeNode>();

			openNodes.Add(new PathTreeNode(startPosition, null, 0));

			while(true)
			{
				if(openNodes.Count == 0)
				{
					depth = 0;
					return null;
				}

				var currentNode = openNodes[0];
				var currentPosition = currentNode.Position;
				if(!closedNodes.Contains(currentNode))
				{
					if(currentPosition == endPosition)
						return CreatePath(currentNode, out depth);

					PathTreeNode left = null, up = null, right = null, down = null;

					left = ProcessNode(currentNode, -1, 0, openNodes, closedNodes);
					up = ProcessNode(currentNode, 0, -1, openNodes, closedNodes);
					right = ProcessNode(currentNode, 1, 0, openNodes, closedNodes);
					down = ProcessNode(currentNode, 0, 1, openNodes, closedNodes);

					if(left != null && up != null)
						ProcessNode(currentNode, -1, -1, openNodes, closedNodes);
					if(right != null && up != null)
						ProcessNode(currentNode, 1, -1, openNodes, closedNodes);
					if(right != null && down != null)
						ProcessNode(currentNode, 1, 1, openNodes, closedNodes);
					if(left != null && down != null)
						ProcessNode(currentNode, -1, 1, openNodes, closedNodes);

					closedNodes.Add(currentNode);
				}
				openNodes.RemoveAt(0);
			}
		}
		#endregion
	}
}
